package tree.segmenttree;

/**
 * @Classname : RangeSumQueryMutable03
 * @Description : 307. 区域和检索 - 数组可修改
 * https://leetcode.cn/problems/range-sum-query-mutable/
 * 线段树：https://oi-wiki.org/ds/seg/
 * 使用数学结论：如果采用堆式存储（2p+1 是 p 的左儿子，2p+2 是 p 的右儿子），若有 n 个叶子结点，则 d 数组的范围小于 4n
 * @Author : chentianyu
 * @Date 2022/12/7 22:11
 */

/**
 * 扩展
 * 方法二：线段树 + 懒惰标记
 * 适用情况：对区间修改
 */
public class RangeSumQueryMutable03 {

    private int[] a;  // 原数组
    private int n;  // 数组大小
    private int[] d;  // 线段树数组
    private int[] b;  // 修改内容
    private int[] v;  // 懒惰标记

    public RangeSumQueryMutable03(int[] nums) {
        a = nums;
        n = nums.length;
        d = new int[4 * n];
        b = new int[4 * n];
        v = new int[4 * n];
        build(0, n - 1, 0);
    }

    public void update(int index, int val) {
        update(index, index, val, 0, n - 1, 0);
    }

    public int sumRange(int left, int right) {
        return search(left, right, 0, n - 1, 0);
    }

    private void build(int s, int t, int p) {
        if (s == t) {
            d[p] = a[s];
        } else {
            int m = s + ((t - s) >> 1);
            build(s, m, 2 * p + 1);
            build(m + 1, t, 2 * p + 2);
            d[p] = d[2 * p + 1] + d[2 * p + 2];
        }
    }

    private int search(int l, int r, int s, int t, int p) {
        int sum = 0;
        if (l <= s && t <= r) {
            sum = d[p];
        } else {
            int m = s + ((t - s) >> 1);
            if (1 == v[p] && s != t) {  // 存在懒惰标记 且 有子节点，则向下更新
                d[2 * p + 1] = (m - s + 1) * b[p];
                b[2 * p + 1] = b[p];
                v[2 * p + 1] = 1;
                d[2 * p + 2] = (t - m) * b[p];
                b[2 * p + 2] = b[p];
                v[2 * p + 2] = 1;
                v[p] = 0;
            }
            if (l <= m) sum += search(l, r, s, m, 2 * p + 1);
            if (r > m) sum += search(l, r, m + 1, t, 2 * p + 2);
        }
        return sum;
    }

    private void update(int l, int r, int c, int s, int t, int p) {
        if (l <= s && t <= r) {
            d[p] = (t - s + 1) * c;
            b[p] = c;  // 记录修改值
            v[p] = 1;  // 懒惰标记
        } else {
            int m = s + ((t - s) >> 1);
            if (1 == v[p] && s != t) {  // 存在懒惰标记 且 有子节点，则向下更新
                d[2 * p + 1] = (m - s + 1) * b[p];
                b[2 * p + 1] = b[p];
                v[2 * p + 1] = 1;
                d[2 * p + 2] = (t - m) * b[p];
                b[2 * p + 2] = b[p];
                v[2 * p + 2] = 1;
                v[p] = 0;
            }
            if (l <= m) update(l, r, c, s, m, 2 * p + 1);
            if (r > m) update(l, r, c, m + 1, t, 2 * p + 2);
            d[p] = d[2 * p + 1] + d[2 * p + 2];  // 【注意】向上更新
        }
    }
}
